/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package Edge;

import BuildGrid.Grid;
import Graph.Car;
import Graph.Parents;
import Graph.Vertex;
import Graph.Vnode;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import static java.lang.Math.abs;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

/**
 *
 * @author 江南才俊周涛涛
 */
public class BuildEdge {

    public static HashMap<Integer, Vertex> All_Vertex = new HashMap<Integer, Vertex>();//地图中的所有结点
//    public static HashMap<Integer, HashSet<Vnode>> neighbors = new HashMap<Integer, HashSet<Vnode>>();
    public static Double[] dvalue;
    private List<Edge> All_Edge = new ArrayList<Edge>(860000);//所有边（含边界点）
    private HashMap<Integer, Edge> Vertex_Edge = new HashMap<Integer, Edge>();//真实结点的真实道路
    public static Grid[][] grids;
    public static int Vertex_num;//真实结点数量
    private int car_num =7500 ;//汽车数量 50000 70000
    private List<Car> cars = new ArrayList<Car>(car_num);//所有汽车
    public static int width = 5000;//格子宽度，设置为静态变量，方便全局使用

    private int Xmin = Integer.MAX_VALUE;//结点的最小横坐标
    private int Ymin = Integer.MAX_VALUE;
    private static int Xmax = Integer.MIN_VALUE;
    private static int Ymax = Integer.MIN_VALUE;

    public static int row;//格子的行数
    public static int column;//格子的列数，此处因为格子的横纵坐标预处理后最大都为1000，000
    private int border_name;//边界点名字
    private int Edge_name = 0;//边的名字

   
    public BuildEdge() {
    }

    //预处理
    public void run() throws IOException {
        //System.out.println("1");
        SetIndex();
        //System.out.println("2");
        init_grids();
        //System.out.println("3");
        buildIndex();
        //System.out.println("4");
        buildedge();
        //System.out.println("5");
        gridsDijk();
        //System.out.println("6");
        init_value();
        //System.out.println("7");
        init_cars();
    }

     //初始化grid[][]
    private void init_grids() {
        grids = new Grid[row][column];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                grids[i][j] = new Grid(i, j);
            }
        }
    }

    //初始化dvalue
    private void init_value() {
        dvalue = new Double[All_Vertex.size() + 1];
        Arrays.fill(dvalue, -1.0);
    }

    //初始化cars
    private void init_cars() {
        long x = System.currentTimeMillis();
        for (int i = 0; i < car_num; i++) {
            Car c = new Car(i);
            add_Car(c);
        }
        long y = System.currentTimeMillis();
        System.out.println("添加汽车时间=" + (y - x) + "毫秒");
    }

    //添加汽车
    public void add_Car(Car c) {
        int e = (int) (Math.random() * (Vertex_Edge.size()));
        int to_name = Vertex_Edge.get(e).to;
        c.to_name = to_name;
        c.dis = (double) (Math.random() * Vertex_Edge.get(e).distence);
        cars.add(c);
        All_Vertex.get(to_name).addCar(c);

        List<Parents> p = All_Vertex.get(to_name).getParents();
        grids[p.get(0).x][p.get(0).y].addActive(to_name, c);
    }

    //更新num辆汽车(删除车并添加车）
    public void update_car(int num) {
        long x = System.currentTimeMillis();
        for (int i = 0; i < num; i++) {
            int car_name = (int) (Math.random() * car_num);//随机找到一辆车
            Car c = cars.get(car_name);
            All_Vertex.get(c.to_name).deleteCar(c);
            if (!All_Vertex.get(c.to_name).isactive) {
                List<Parents> p = All_Vertex.get(c.to_name).getParents();
                grids[p.get(0).x][p.get(0).y].deleteActive(c.to_name);
            }
            add_Car(c);
        }
        long y = System.currentTimeMillis();
        System.out.println("更新 " + num + " 辆汽车的时间 = " + (y - x) + "毫秒");
    }

    //配置girds
    private void gridsDijk() {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                grids[i][j].buildgraph();
            }
        }

    }


    //读取坐标文件，设置最小XY坐标
    private void SetIndex() throws FileNotFoundException, IOException {
        int name, x, y;
//        File file = new File("D:\\本科生导师制\\出租车论文\\地图\\USA-road-d.NY.co\\USA-road-d.NY.txt");
//        File file = new File("D:\\本科生导师制\\出租车论文\\弗罗里达州\\USA-road-d.FLA.co");
        File file = new File("C:\\Users\\ASUS\\Desktop\\纽约\\USA-road-d.NY.txt");
        if (file.isFile() && file.exists()) { //判断文件是否存在
            InputStreamReader read = new InputStreamReader(new FileInputStream(file));//暂时没有用GBK编码格式
            BufferedReader bufferedReader = new BufferedReader(read);
            String lineText = null;
            while ((lineText = bufferedReader.readLine()) != null) {
                if (lineText.charAt(0) == 'v') {
                    String[] s = lineText.split("\\s+");
                    name = Integer.parseInt(s[1]);
                    x = Integer.parseInt(s[2]);
                    y = Integer.parseInt(s[3]);
                    if (x < Xmin) {
                        Xmin = x;
                    }
                    if (x > Xmax) {
                        Xmax = x;
                    }
                    if (y < Ymin) {
                        Ymin = y;
                    }
                    if (y > Ymax) {
                        Ymax = y;
                    }
                }
            }

            read.close();
            Ymax = Ymax - Ymin;
            Xmax = Xmax - Xmin;
            row = Ymax / width + 1;
            column = Xmax / width + 1;
            /*System.out.println("row=" + row);
            System.out.println("column=" + column);
            System.out.println("Xmin=" + Xmin);
            System.out.println("Xmax=" + Xmax);
            System.out.println("Ymin=" + Ymin);
            System.out.println("Ymax=" + Ymax);*/
        }
    }

    //读取坐标文件，添加Vertex进入All_Vertex，以及分进各个grids中
    private void buildIndex() throws FileNotFoundException, IOException {
        int name, x, y;
//        File file = new File("D:\\本科生导师制\\出租车论文\\地图\\USA-road-d.NY.co\\USA-road-d.NY.txt");
//  File file = new File("D:\\本科生导师制\\出租车论文\\弗罗里达州\\USA-road-d.FLA.co");
        File file = new File("C:\\Users\\ASUS\\Desktop\\纽约\\USA-road-d.NY.txt");
        if (file.isFile() && file.exists()) { //判断文件是否存在
            InputStreamReader read = new InputStreamReader(new FileInputStream(file));//暂时没有用GBK编码格式
            BufferedReader bufferedReader = new BufferedReader(read);
            String lineText = null;
            while ((lineText = bufferedReader.readLine()) != null) {
                if (lineText.charAt(0) == 'v') {
                    String[] s = lineText.split("\\s+");
                    name = Integer.parseInt(s[1]);
                    x = Integer.parseInt(s[2]) - Xmin;
                    y = Integer.parseInt(s[3]) - Ymin;
                    Vertex temp = new Vertex(name, x, y);
                    temp.isvertex = true;

                    All_Vertex.put(name, temp);
                    Vertex_in_grid(name, temp);
                }
            }
            border_name = All_Vertex.size();
            Vertex_num = border_name;
            read.close();
        }
    }

    //提取文件中的关系，构造原关系edge，和边界点edge，以及边界点，并将它们放入各个格子中去
    private void buildedge() throws FileNotFoundException, IOException {
        int from, to, distence, times = 0;
//        File file = new File("D:\\本科生导师制\\出租车论文\\地图\\USA-road-d.NY.gr\\USA-road-d.NY.txt");
// File file = new File("D:\\本科生导师制\\出租车论文\\弗罗里达州\\USA-road-d.FLA.gr");
        File file = new File("C:\\Users\\ASUS\\Desktop\\纽约\\USA-road-d.NY(1).txt");
        if (file.isFile() && file.exists()) { //判断文件是否存在
            InputStreamReader read = new InputStreamReader(new FileInputStream(file));//暂时没有考虑到编码格式
            BufferedReader bufferedReader = new BufferedReader(read);
            String lineText = null;
            while ((lineText = bufferedReader.readLine()) != null) {
                if (lineText.charAt(0) == 'a') {
                    String[] s = lineText.split("\\s+");
                    if (times == 0) {
                        from = Integer.parseInt(s[1]);
                        to = Integer.parseInt(s[2]);
                        distence = Integer.parseInt(s[3]);
                        Edge ft = new Edge(from, to, distence);
                        Edge tf = new Edge(to, from, distence);

                        Vertex_Edge.put(Edge_name, ft);
                        Edge_name++;
                        Vertex_Edge.put(Edge_name, tf);
                        Edge_name++;
                        buildsub_edge(from, to, distence);

                        times++;
                    } else {
                        times = 0;
                    }

                }
            }

            read.close();
        }
    }

//    找出v1和v2中与格子相交的边界点，以及包含边界的的关系
    private void buildsub_edge(int v1, int v2, int d) {
        DecimalFormat df = new DecimalFormat("#.00");

        Vertex pre, next, temp;

        pre = vertex_is_border(All_Vertex.get(v1));
        next = vertex_is_border(All_Vertex.get(v2));

        if (pre.x > next.x) {
            temp = pre;
            pre = next;
            next = temp;
        }

//        if (All_Vertex.get(v1).x <= All_Vertex.get(v2).x) {
//            pre = All_Vertex.get(v1);
//            next = All_Vertex.get(v2);
//        } else {
//            pre = All_Vertex.get(v2);
//            next = All_Vertex.get(v1);
//        }//v1和v2中，横坐标较小的那个点赋值给pre，较大的那个点赋值给next
        if (pre.x == next.x) {//竖直直线
            double ydis, dis;
            if (pre.y > next.y) {
                temp = pre;
                pre = next;
                next = temp;
            }
//            if (All_Vertex.get(v1).y <= All_Vertex.get(v2).y) {
//                pre = All_Vertex.get(v1);
//                next = All_Vertex.get(v2);
//            } else {
//                pre = All_Vertex.get(v2);
//                next = All_Vertex.get(v1);
//            }//v1和v2中，纵坐标较小的那个点赋值给pre，较大的那个点赋值给next
            ydis = next.y - pre.y;

            for (int i = ((int) pre.y / width + 1) * width; i < next.y; i = i + width) {
                border_name++;
                Vertex border = new Vertex(border_name, pre.x, i);
                dis = (double) (i - pre.y) / ydis * d;
                dis = Double.valueOf(df.format(dis));

                All_Vertex.put(border_name, border);

//                HashSet<Vnode> hs = new HashSet<Vnode>();
//                neighbors.put(border_name, hs);
                Border_in_grid(border_name, border);
                Edge pb = new Edge(pre.Vertex_name, border_name, dis);
                Edge bp = new Edge(border_name, pre.Vertex_name, dis);

                All_Edge.add(pb);
                All_Edge.add(bp);
                Edge_in_grid(pb, bp);
                pre = border;

            }
            //边界点与最后一个点相连
            dis = (double) (next.y - pre.y) / ydis * d;
            dis = Double.valueOf(df.format(dis));
            Edge bn = new Edge(border_name, next.Vertex_name, dis);
            Edge nb = new Edge(next.Vertex_name, border_name, dis);
            All_Edge.add(bn);
            All_Edge.add(nb);
            Edge_in_grid(bn, nb);
            return;

        } else if (pre.y == next.y) {//水平直线
            double xdis, dis;
            xdis = next.x - pre.x;

            for (int i = ((int) pre.x / width + 1) * width; i < next.x; i = i + width) {
                border_name++;
                Vertex border = new Vertex(border_name, i, pre.y);
                dis = (double) (i - pre.x) / xdis * d;
                dis = Double.valueOf(df.format(dis));

                All_Vertex.put(border_name, border);
//                HashSet<Vnode> hs = new HashSet<Vnode>();
//                neighbors.put(border_name, hs);

                Border_in_grid(border_name, border);
                Edge pb = new Edge(pre.Vertex_name, border_name, dis);
                Edge bp = new Edge(border_name, pre.Vertex_name, dis);

                All_Edge.add(pb);
                All_Edge.add(bp);
                Edge_in_grid(pb, bp);
                pre = border;

            }
            //边界点与最后一个点相连
            dis = (double) (next.x - pre.x) / xdis * d;
            dis = Double.valueOf(df.format(dis));
            Edge bn = new Edge(border_name, next.Vertex_name, dis);
            Edge nb = new Edge(next.Vertex_name, border_name, dis);
            All_Edge.add(bn);
            All_Edge.add(nb);
            Edge_in_grid(bn, nb);
            return;

        } else {
            double xdis = next.x - pre.x,
                    ydis = next.y - pre.y,
                    tan = ydis / xdis,
                    cot = xdis / ydis,
                    dis;

            List<Vertex> temps = new ArrayList<Vertex>();//临时存储边界点，排序后clear。如果知道边界点的大致数量，可以一开始就分配，以免List扩容时浪费时间
            for (int i = ((int) pre.x / width + 1) * width; i < next.x; i = i + width) {
                border_name++;
                Vertex border = new Vertex(border_name, i, f(i, pre.x, pre.y, tan));
                All_Vertex.put(border_name, border);

//                HashSet<Vnode> hs = new HashSet<Vnode>();
//                neighbors.put(border_name, hs);
                Border_in_grid(border_name, border);
                temps.add(border);
            }
            double ymin, ymax;
            if (pre.y < next.y) {
                ymin = pre.y;
                ymax = next.y;
            } else {
                ymin = next.y;
                ymax = pre.y;
            }
            for (int i = ((int) ymin / width + 1) * width; i < ymax; i = i + width) {
                border_name++;
                Vertex border = new Vertex(border_name, g(i, pre.x, pre.y, cot), i);
                All_Vertex.put(border_name, border);

//                HashSet<Vnode> hs = new HashSet<Vnode>();
//                neighbors.put(border_name, hs);
                Border_in_grid(border_name, border);
                temps.add(border);
            }
            Collections.sort(temps, new CostComparator());
            for (int i = 0; i < temps.size(); i++) {
                dis = (double) (temps.get(i).x - pre.x) / xdis * d;
                dis = Double.valueOf(df.format(dis));
                Edge pb = new Edge(temps.get(i).Vertex_name, pre.Vertex_name, dis);
                Edge bp = new Edge(pre.Vertex_name, temps.get(i).Vertex_name, dis);
                All_Edge.add(pb);
                All_Edge.add(bp);
                Edge_in_grid(pb, bp);
                pre = temps.get(i);
            }
            dis = (double) (next.x - pre.x) / xdis * d;
            dis = Double.valueOf(df.format(dis));
            Edge bn = new Edge(pre.Vertex_name, next.Vertex_name, dis);
            Edge nb = new Edge(next.Vertex_name, pre.Vertex_name, dis);
            All_Edge.add(bn);
            All_Edge.add(nb);
            Edge_in_grid(bn, nb);
            temps.clear();
        }
    }

    //将真实结点加入格子中去
    private void Vertex_in_grid(int name, Vertex temp) {
        Vertex temp3 = new Vertex(temp);
        List<Parents> parents = temp.getParents();
        int x, y;
        x = parents.get(0).x;
        y = parents.get(0).y;
        grids[x][y].put_vertex(name, temp3);
    }

    //将边界点加入到格子中去
    private void Border_in_grid(int name, Vertex temp) {
        List<Parents> parents = temp.getParents();
        for (int i = 0; i < parents.size(); i++) {
            Vertex temp2 = new Vertex(temp);
            int x = parents.get(i).x;
            int y = parents.get(i).y;
            grids[x][y].putmap(name, temp2);
        }
    }

    //将边添加到格子中去
    private void Edge_in_grid(Edge f, Edge t) {
        List<Parents> intersection = new ArrayList<Parents>(All_Vertex.get(f.from).getParents());
        List<Parents> t_parents = All_Vertex.get(f.to).getParents();

        intersection.retainAll(t_parents);
        int x, y;
        for (int i = 0; i < intersection.size(); i++) {
            x = (int) intersection.get(i).x;
            y = (int) intersection.get(i).y;

            grids[x][y].edges.add(f);
            grids[x][y].edges.add(t);
        }

    }

    //判断内部结点是否是边界点，如果内部结点是边界点，则添加一个点为边界点，将它与内部结点相连，距离为0 
    private Vertex vertex_is_border(Vertex temp) {
        if (((int) temp.y % width == 0 || (int) temp.x % width == 0)) {//还没有被判断成边界点
            if (temp.isborder == false) {
                border_name++;
                temp.isborder = true;//isborder改为true
                Vertex border = new Vertex(border_name, temp.x, temp.y);
                temp.border_name = border_name;
                All_Vertex.put(border_name, border);

//                HashSet<Vnode> hs = new HashSet<Vnode>();
//                neighbors.put(border_name, hs);
                Border_in_grid(border_name, border);
                Edge vb = new Edge(temp.Vertex_name, border_name, 0);
                Edge bv = new Edge(border_name, temp.Vertex_name, 0);

                All_Edge.add(vb);
                All_Edge.add(bv);
                Edge_in_grid(vb, bv);
            } else {
                return All_Vertex.get(temp.border_name);
            }

        }
        return temp;
    }

    //函数 y-y1=tan(x-x1)中，输入x得到y
    private double f(double x, double x1, double y1, double tan) {
        return tan * (x - x1) + y1;//y-y1=k(x-x1)
    }

    //函数 x-x1=cot(y-y1)中，输入y得到x
    private double g(double y, double x1, double y1, double cot) {
        return cot * (y - y1) + x1;
    }

    //compare函数，比较Vertex的横坐标，把横坐标从小到大进行排序
    static class CostComparator implements Comparator {

        public int compare(Object object1, Object object2) {// 实现接口中的方法  
            Vertex p1 = (Vertex) object1; // 强制转换  
            Vertex p2 = (Vertex) object2;
            return Double.compare(p1.x, p2.x);
        }
    }
}
